﻿
// check if the two queens attack each other
let conflict (i1, j1) (i2, j2) =
    if i1 = i2 || j1 = j2 || abs(i1-i2) = abs(j1-j2) then
        true
    else
        false

// check if a new position is valid to a list of other (valid) positions
let check (newPos:int*int) (posList: (int*int) list) =
    posList
    |> List.exists (fun pos -> conflict newPos pos)
    |> not

// the backtracking procedure to get all solutions
let rec searchQueen i n sols =
    if i = n then
        sols
    else
        let newSols =
            sols
            |> List.map (fun sol ->
                [0..n-1]
                |> List.filter (fun j -> check (i,j) sol)
                |> List.map (fun j -> (i,j)::sol)
                )
            |> List.concat
        searchQueen (i+1) n newSols

let allSolutions = searchQueen 0 8 [[]]

allSolutions |> List.length

